【进阶一】Python实现MDCVRP常见求解算法 |
您所在的位置：网站首页 › python 路径优化 › 【进阶一】Python实现MDCVRP常见求解算法 |
【进阶一】Python实现MDCVRP常见求解算法
|
基于python语言，实现经典遗传算法（GA）对多车场车辆路径规划问题（MDCVRP）进行求解。 目录 往期优质资源1. 适用场景2. 求解效果3. 代码分析4. 数据格式5. 分步实现6. 完整代码参考 往期优质资源 python实现6种智能算法求解CVRP问题python实现7种智能算法求解MDVRP问题python实现7种智能算法求解MDVRPTW问题Python版MDHFVRPTW问题智能求解算法代码【TS算法】Python版MDHFVRPTW问题智能求解算法代码【SA算法】Python版MDHFVRPTW问题智能求解算法代码【GA算法】Python版MDHFVRPTW问题智能求解算法代码【DPSO算法】Python版MDHFVRPTW问题智能求解算法代码【DE算法】Python版MDHFVRPTW问题智能求解算法代码【ACO算法】Python版HVRP问题智能求解算法代码【GA算法】Python版HVRP问题智能求解算法代码【DPSO算法】 1. 适用场景 求解MDCVRP 问题车辆类型单一车辆容量不小于需求节点最大需求多车辆基地各车场车辆总数满足实际需求 2. 求解效果（1）收敛曲线 车俩路径规划问题按照车场数量可分为单一车场路径规划问题和多车场路径规划问题。针对单一车场条件下仅考虑车辆容量限制的路径规划问题前边帖子中已实现GA算法求解，本文采用GA算法对多车场条件下仅考虑车辆容量限制的路径规划问题进行求解。为了保持代码的延续性以及求解思路的一致性，这里对上述GA算法代码进行如下主要修正实现MDCVRP问题的求解。 Model数据结构类中采用demand_dict属性存储需求节点集合，depot_dict属性储存车场节点集合，demand_id_list属性储存需求节点id集合，distance_matrix属性储存任意节点间的欧式距离；Node数据结构类中去掉node_seq属性，增加depot_capacity属性记录车场的车队限制splitRoutes函数中分割车辆路径时分配最近车场作为其车辆提供基地（满足车场车队数量限制） 4. 数据格式以csv文件储存数据，其中demand.csv文件记录需求节点数据，共包含需求节点id，需求节点横坐标，需求节点纵坐标，需求量；depot.csv文件记录车场节点数据，共包含车场id，车场横坐标，车场纵坐标，车队数量。需要注意的是：需求节点id应为整数，车场节点id任意，但不可与需求节点id不可重复。 可参考github主页相关文件。 5. 分步实现（1）数据结构 定义Sol()类，Node()类，Model()类，其属性如下表： Sol()类，表示一个可行解 属性描述node_id_list需求节点id有序排列集合，对应TSP的解obj优化目标值fit解的适应度routes车辆路径集合，对应MDCVRP的解 Node()类，表示一个网络节点 属性描述id物理节点id，需唯一x_coord物理节点x坐标y_coord物理节点y坐标demand物理节点需求depot_capacity车辆基地车队规模 Model()类，存储算法参数 属性描述best_sol全局最优解，值类型为Sol()demand_dict需求节点集合（字典），值类型为Node()depot_dict车场节点集合（字典），值类型为Node()demand_id_list需求节点id集合sol_list种群，值类型为Sol()distance_matrix节点距离矩阵opt_type优化目标类型，0：最小车辆数，1：最小行驶距离vehicle_cap车辆容量pc交叉概率pm突变概率n_select优良个体选择数量popsize种群规模（2）文件读取 def readCsvFile(demand_file,depot_file,model): with open(demand_file,'r') as f: demand_reader=csv.DictReader(f) for row in demand_reader: node = Node() node.id = int(row['id']) node.x_coord = float(row['x_coord']) node.y_coord = float(row['y_coord']) node.demand = float(row['demand']) model.demand_dict[node.id] = node model.demand_id_list.append(node.id) with open(depot_file,'r') as f: depot_reader=csv.DictReader(f) for row in depot_reader: node = Node() node.id = row['id'] node.x_coord=float(row['x_coord']) node.y_coord=float(row['y_coord']) node.depot_capacity=float(row['capacity']) model.depot_dict[node.id] = node（3）计算距离矩阵 def calDistance(model): for i in range(len(model.demand_id_list)): from_node_id = model.demand_id_list[i] for j in range(i+1,len(model.demand_id_list)): to_node_id=model.demand_id_list[j] dist=math.sqrt( (model.demand_dict[from_node_id].x_coord-model.demand_dict[to_node_id].x_coord)**2 +(model.demand_dict[from_node_id].y_coord-model.demand_dict[to_node_id].y_coord)**2) model.distance_matrix[from_node_id,to_node_id]=dist model.distance_matrix[to_node_id,from_node_id]=dist for _,depot in model.depot_dict.items(): dist = math.sqrt((model.demand_dict[from_node_id].x_coord - depot.x_coord) ** 2 + (model.demand_dict[from_node_id].y_coord -depot.y_coord)**2) model.distance_matrix[from_node_id, depot.id] = dist model.distance_matrix[depot.id, from_node_id] = dist（4）初始解生成 def generateInitialSol(model): demand_id_list=copy.deepcopy(model.demand_id_list) for i in range(model.popsize): seed=int(random.randint(0,10)) random.seed(seed) random.shuffle(demand_id_list) sol=Sol() sol.node_id_list=copy.deepcopy(demand_id_list) model.sol_list.append(sol)（5）适应度计算 适应度计算依赖" splitRoutes “函数对TSP可行解分割得到车辆行驶路线和所需车辆数，在得到各车辆形式路线后在满足车场车队规模条件下分配最近车场，” calDistance "函数计算行驶距离。 def selectDepot(route,depot_dict,model): min_in_out_distance=float('inf') index=None for _,depot in depot_dict.items(): if depot.depot_capacity>0: in_out_distance=model.distance_matrix[depot.id,route[0]]+model.distance_matrix[route[-1],depot.id] if in_out_distance= 0: route.append(node_id) remained_cap = remained_cap - model.demand_dict[node_id].demand else: route,depot_dict=selectDepot(route,depot_dict,model) vehicle_routes.append(route) route = [node_id] num_vehicle = num_vehicle + 1 remained_cap =model.vehicle_cap - model.demand_dict[node_id].demand route, depot_dict = selectDepot(route, depot_dict, model) vehicle_routes.append(route) return num_vehicle,vehicle_routes def calRouteDistance(route,model): distance=0 for i in range(len(route)-1): from_node=route[i] to_node=route[i+1] distance +=model.distance_matrix[from_node,to_node] return distance def calFit(model): #calculate fit value：fit=Objmax-obj max_obj=-float('inf') best_sol=Sol()#record the local best solution best_sol.obj=float('inf') for sol in model.sol_list: node_id_list=sol.node_id_list num_vehicle, vehicle_routes = splitRoutes(node_id_list, model) if model.opt_type==0: sol.obj=num_vehicle sol.routes=vehicle_routes if sol.obj>max_obj: max_obj=sol.obj if sol.objmax_obj: max_obj=sol.obj if sol.obj |
（2）车辆路径 
【本文地址】
今日新闻 |
推荐新闻 |